package x.y.z;

import java.util.*;

public class LeetCode_0017 {
    private List<String> result = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        Map<Character, char[]> cache = new HashMap<>();
        cache.put('2', "abc".toCharArray());
        cache.put('3', "def".toCharArray());
        cache.put('4', "ghi".toCharArray());
        cache.put('5', "jkl".toCharArray());
        cache.put('6', "mno".toCharArray());
        cache.put('7', "pqrs".toCharArray());
        cache.put('8', "tuv".toCharArray());
        cache.put('9', "wxyz".toCharArray());

        dfs(digits, 0, new LinkedList<>(), cache);

        return result;
    }

    private void dfs(String digits, int index, LinkedList<String> path, Map<Character, char[]> cache) {
        if (digits.length() == path.size()) {
            result.add(String.join("", path));
            return;
        }

        for (char ch : cache.get(digits.charAt(index))) {
            path.add(ch + "");
            dfs(digits, index + 1, path, cache);
            path.removeLast();
        }
    }
}
